package linkedlist.other;

import linkedlist.Node;
import linkedlist.create.RecursionLinkedCreator;

/**
 * 查找两个链表第一个公共节点，因为单向链表，所以第一个公共节点后面的节点肯定相同，y形结构。后面是一样的，就把前面多余的比较去掉
 */
public class FindCommonNode {


  public Node findFirstCommon(Node head1, Node head2) {
    if (head1 == null || head2 == null) {
      return null;
    }

    int head1Length = getLength(head1);
    int head2Length = getLength(head2);

    int step = 0;
    if (head1Length > head2Length) {
      step = head1Length - head2Length;
      while (step != 0) {
        head1 = head1.getNext();
        step--;
      }
    } else {
      step = head2Length - head1Length;
      while (step != 0) {
        head2 = head2.getNext();
        step--;
      }
    }
    //现在两者的长度是相同的了
    while (head1 != head2) {
      head1 = head1.getNext();
      head2 = head2.getNext();
    }

    return head1;


  }


  public int getLength(Node head) {
    int length = 0;
    while (head != null) {
      head = head.getNext();
      length++;
    }
    return length;
  }


  public static void main(String args[]) {
    RecursionLinkedCreator creator = new RecursionLinkedCreator();

    Node node1 = new Node(1);
    Node node2 = new Node(2);
    Node node3 = new Node(3);
    Node node4 = new Node(4);
    Node node5 = new Node(5);
    Node node6 = new Node(6);
    Node node7 = new Node(7);
    //构建第一个链表 1，2，3，6，7
    node1.setNext(node2);
    node2.setNext(node3);
    node3.setNext(node6);
    node6.setNext(node7);

    //构建第二个链表5，6，7
    node5.setNext(node6);

    FindCommonNode FindCommonNode = new FindCommonNode();
    Node commonNode = FindCommonNode.findFirstCommon(node1, node5);
    if (commonNode == null) {
      System.out.println("没有公共节点");
    } else {
      System.out.println(commonNode.getData());
    }


  }

}
